
// 【题目】力扣84. 柱状图中最大的矩形
// 【难度】困难
// 【提交】https://leetcode.cn/problems/largest-rectangle-in-histogram/submissions/664837460/
// 【标签】单调栈；数组
//
// Created by 1 on 2025/9/21.
//
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        int ans = 0;
        // 枚举左边界
        for (int left = 0; left < n; ++left) {
            int minHeight = INT_MAX;
            // 枚举右边界
            for (int right = left; right < n; ++right) {
                // 确定高度
                minHeight = min(minHeight, heights[right]);
                // 计算面积
                ans = max(ans, (right - left + 1) * minHeight);
            }
        }
        return ans;
    }
};

